#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int ret = 0;
        for (int i = 0; i < k; i++)
        {
            sort(nums.begin(), nums.end());
            nums[0] = -nums[0];
        }
        for (auto& e : nums)
            ret += e;
        return ret;
    }
};

class Solution {
public:
    static bool abs_cmp(int a, int b) {
        return abs(a) > abs(b);
    }

    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int ret = 0;
        sort(nums.begin(), nums.end(), abs_cmp);
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0 && k>0)
            {
                nums[i] = -nums[i];
                k--;
            }
        }
        while (k--)
            nums[nums.size() - 1] = -nums[nums.size() - 1];
        for (auto& e : nums)
            ret += e;
        return ret;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int ret = 0;
        int realSum = 0;
        int curSum = 0;
        for (int i = 0; i < gas.size(); i++)
        {
            realSum += gas[i] - cost[i];
            curSum += gas[i] - cost[i];
            if (curSum < 0)
            {
                ret = i + 1;
                curSum = 0;
            }
        }
        if (realSum < 0)
            return -1;
        return ret;
    }
};

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> target(ratings.size(), 1);
        int ret = 0;
        for (int i = 0; i < ratings.size() - 1; i++)
        {
            if (ratings[i] < ratings[i + 1])
                target[i + 1] = target[i] + 1;
        }
        for (int i = ratings.size() - 1; i >= 1; i--)
        {
            if (ratings[i] < ratings[i - 1])
                target[i - 1] = max(target[i] + 1, target[i - 1]);
        }
        for (auto e : target)
            ret += e;
        return ret;
    }
};